package com.fufu.leetcode;

/**
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 *
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 */

import java.util.Stack;

/**
 * @author: BlcakTiger
 * @date: 2023/2/27 19:06
 * @contact: hsf6661@163.com
 */
public class 两数相加 {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(9);
        ListNode l2 = new ListNode(9);
        ListNode l3 = new ListNode(9);
        ListNode l4 = new ListNode(9);
        ListNode l5 = new ListNode(9);
        ListNode l6 = new ListNode(9);
        ListNode l7 = new ListNode(9);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = l6;
        l6.next = l7;

        ListNode n1 = new ListNode(9);
        ListNode n2 = new ListNode(9);
        ListNode n3 = new ListNode(9);
        ListNode n4 = new ListNode(9);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        ListNode listNode = addTwoNumbers(l1, n1);
        System.out.println(listNode);

    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //辅助节点
        ListNode temp = new ListNode();
        //结果集节点
        ListNode resHead = null;
        //获取头结点标志位
        boolean flag = true;
        //进位
        int ci = 0;

        //计算
        while (true){
            //1.l1和l2都不为空
            if (l1!=null && l2!=null){
                //判断是否可以进位
                if ((l1.val+l2.val+ci)/10>0){
                    temp.val = (l1.val+l2.val+ci)%10;
                    ci = (l1.val+l2.val+ci)/10;
                }else{//不可以进位
                    temp.val = l1.val+l2.val+ci;
                    ci = 0;
                }
                //指针后移
                l1 = l1.next;
                l2 = l2.next;

            }else{
                //l1不为空
                if (l1!=null){
                    //判断进位
                    if ((l1.val+ci)/10>0){
                        temp.val = (l1.val+ci)%10;
                        ci = (l1.val+ci)/10;
                    }else {
                        temp.val = l1.val+ci;
                        ci = 0;
                    }
                    //指针后移
                    l1 = l1.next;
                }else if(l2!=null){ //l2不为空
                    //判断进位
                    if((l2.val+ci)/10>0){
                        temp.val = (l2.val+ci)%10;
                        ci = (l2.val+ci)/10;
                    }else{
                        temp.val = l2.val+ci;
                        ci = 0;
                    }
                    l2 = l2.next;
                }
            }
            //只执行一次，获取first节点
            if (flag){
                resHead = temp;
                flag = !flag;
            }
            //当都为空时直接结束，后面不再创建新的节点
            if (l1==null && l2==null){
                break;
            }
            temp.next = new ListNode();
            temp = temp.next;
        }
        //如果循环结束后ci进位不为0，还需要在链表末尾补一个节点
        if (ci!=0){
            temp = resHead;
            while (temp.next!=null){
                temp = temp.next;
            }
            temp.next = new ListNode(ci);
        }

        return resHead;
    }

}

